This invention relates generally to computer software and more specifically to software data structures and abstract data types.
Hash-based data structures (hash tables) are commonly used software data structures. Hash tables use a hash function to map certain unique identifiers (e.g., names) to their associated values (e.g., personnel records). A hash function transforms the identifier (called a key) into a value (called a hash code) that is then further transformed into an index that represents an element of an array (called a slot) where the associated value would reside.
In practice, resource limitations and other design considerations dictate that there will not be enough slots, nor will the hash function be so perfect as to map each possible key to a unique slot index. The common case where more than one identifier hashes to the same index is called a collision. When a collision occurs, a hash table takes measures to disambiguate the items, typically by means of a traversable data structure like a linked list or chain.
A hash table with no collisions is among the most efficient data structures available with respect to insertion, deletion and lookup. In such a case as there are no collisions, the average cost for each lookup is effectively the cost of the hash function, and is independent of the number of items in or the capacity of the table. When a hash table has collisions, the lookup efficiency degrades to approach that of a traversable data structure, a function of the number of items in the traversable structure.
It is advantageous to employ a method by which collisions would be minimized.